package SlideWindows;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
 *
 * 示例：
 *
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 *
 */
public class L76_MinSubstringWin {

    /**
     * 滑动窗口，i, j都是从左边开始
     * 对于AXXXXBCXXABC
     * 我滑动窗口，怎么确定能找到 ABC，画图就知道了。
     *
     * 如果用最大的窗口缩小，会有问题，必须还是要左右开始起来
     */
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> t_map = new HashMap<>(), s_map = new HashMap<>();

        for(int i=0; i<t.length();i++) 
            t_map.put(t.charAt(i), t_map.getOrDefault(t.charAt(i),0) + 1);
            
        int min = Integer.MAX_VALUE, left=0, right=0;
        String res="";
        for( left=0; right < s.length(); ++right){
            //右移窗口
            s_map.put(s.charAt(right), s_map.getOrDefault(s.charAt(right),0)+1);

            //检查是否合法
            while (check(s_map, t_map)){
                if( right-left< min){//合法，然后，取结果，同时左移
                    min = right-left + 1;
                    res = s.substring(left, right+1);
                }
                //左移成功，就开始动作窗口，但是，这里不是remove，是-1
                s_map.put(s.charAt(left), s_map.get(s.charAt(left)) -1);
                left++;
            }
        }

        return res;
    }

    boolean check(HashMap<Character, Integer> s_map, HashMap<Character, Integer> t_map){
        for(Map.Entry<Character, Integer> entry: t_map.entrySet()){
            if(s_map.containsKey(entry.getKey())// 这个<= 很重要， 不能相等，因为可能会有多个
                    && entry.getValue() <= s_map.get(entry.getKey())){
            }else{
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args){
        L76_MinSubstringWin l = new L76_MinSubstringWin();
        l.minWindow("ADOBECODEBANC", "ABC");
    }
}
